#include "main/utils.h"
using namespace std;

class Solution {
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
      stack<pair<int, int>> remain_status;
      remain_status.push({0, 0});
      auto hash_function = [](const pair<int, int>& o) {
        return hash<int>()(o.first) ^ hash<int>()(o.second);
      };
      unordered_set<pair<int, int>, decltype(hash_function)> helper_set(0, hash_function);
      while (!remain_status.empty()) {
        auto cur_status = remain_status.top();
        if (helper_set.count(cur_status) > 0) {
          remain_status.pop();
          continue;
        }
        helper_set.insert(cur_status);
        remain_status.pop();
        int remain_x = cur_status.first;
        int remain_y = cur_status.second;
        if (remain_x == targetCapacity ||
            remain_y == targetCapacity ||
            remain_x + remain_y == targetCapacity) {
          return true;
        }

        remain_status.push({jug1Capacity, remain_y});
        remain_status.push({remain_x, jug2Capacity});
        remain_status.push({0, remain_y});
        remain_status.push({remain_x, 0});
        remain_status.push({remain_x - min(remain_x, jug2Capacity - remain_y), remain_y + min(remain_x, jug2Capacity - remain_y)});
        remain_status.push({remain_x + min(jug1Capacity - remain_x, remain_y), remain_y - min(jug1Capacity - remain_x, remain_y)});
      }
      return false;
    }

    // bool canMeasureWater1(int x, int y, int z) {
    //   if (x + y < z) {
    //     return false;
    //   }
    //   if (x == 0 || y == 0) {
    //     return z == 0 || x + y == z;
    //   }
    //   return z % gcd(x, y) == 0;
    // }
};

int main() {
  int jug1_capacity = 34;
  int jug2_capacity = 5;
  int target_capacity = 6;
  Solution su;
  cout << su.canMeasureWater(jug1_capacity, jug2_capacity, target_capacity) << endl;
  // cout << su.canMeasureWater1(jug1_capacity, jug2_capacity, target_capacity) << endl;

  return 0;
}
